package com.aqie.medium.dynamicProgram;

/**
 * 309 DP
 * 1, 不能同时参与多笔交易
 * 2, 卖出股票后，你无法在第二天买入股票
 */
public class MaxProfit {
    /**
     * 1, 3ms
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        //持有成本
        int[] hold = new int[prices.length];
        //卖出获利
        int[] profit = new int[prices.length];
        hold[0] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (i == 1) {
                hold[i] = Math.max(hold[i - 1], -prices[1]);
            } else {
                hold[i] = Math.max(hold[i - 1], profit[i - 2] - prices[i]);
            }
            //当前不卖出，或者卖出，取最大值
            profit[i] = Math.max(profit[i - 1], hold[i - 1] + prices[i]);
        }
        return profit[prices.length - 1];
    }


}
